Providing on-street parking navigation options is an area of interest for many navigation service providers and original equipment manufacturers (OEMs). To help provide such options, service providers often use parking duration data to model parking behaviors along various streets. One source of this data is from connected cars or other vehicles that report parking related data (e.g., park in and park out events) as they travel in a road network. However, for privacy reasons, it is not always possible to determine parking duration data directly from connected vehicles. This is because knowledge of the identity of a specific vehicle has been traditionally required to link a reported park in event with a park out event to calculate a parking duration for the vehicle. Accordingly, service providers face significant technical challenges to determining parking durations from parking data that has been anonymized with respect to the vehicle from which the data was collected, or for which there is no association between a given park in event and a corresponding park out event.